P4900 食堂 发布于 2020-09-12 | 分类于 数学 、 数论 | 4分钟 | 576字数 题目需要求的是这个式子: ∑i=AB∑j=1i{ij}\sum_{i=A}^B\sum_{j=1}^i \{\frac{i}{j}\} i=A∑Bj=1∑i{ji} 阅读全文 »
P3327 [SDOI2015]约数个数和 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 5分钟 | 744字数 首先有一个公式: d(ij)=∑x∣i∑y∣j[(i,j)=1]d(ij)=\sum_{x|i}\sum_{y|j}[(i,j)=1] d(ij)=x∣i∑y∣j∑[(i,j)=1] 阅读全文 »
CF464D World of Darkraft - 2 发布于 2020-09-12 | 分类于 概率dp | 3分钟 | 501字数 首先明确一点,所有装备的期望相同,只需求出任意一种后答案乘 kkk 即可。 令 dp[i][j]dp[i][j]dp[i][j] 表示还需要打 iii 只怪,装备等级为 jjj 的金币数量期望。 那么有三种情况: 阅读全文 »
CF398B Painting The Wall 发布于 2020-09-12 | 分类于 概率dp | 5分钟 | 833字数 先考虑所有格子均未涂色的情况。 因为格子的涂色只会影响一行一列,所以可以设 dp(i,j)dp(i,j)dp(i,j) 表示还需要涂 iii 行 , jjj 列的期望步数。 1.涂色格所在行列均未染色,由 dp(i−1,j−1)dp(i-1,j-1)dp(i−1,j−1) 转移,概率为 in×jn\frac{i}{n} \times \frac{j}{n}ni×nj 阅读全文 »
P3501 [POI2010]ANT-Antisymmetry 发布于 2020-09-12 | 分类于 回文自动机 | 2分钟 | 296字数 看到求回文串就想到 PAM\text{PAM}PAM 。 因为只有 0,10,10,1 所以判断条件改成等于。 不过这道题满足题意的串长度一定为偶,所以不能走到 −1-1−1 根。 阅读全文 »
P1891 疯狂LCM 发布于 2020-09-12 | 分类于 数论 | 4分钟 | 516字数 ∑i=1nlcm(i,n)\sum_{i=1}^n lcm(i,n) i=1∑nlcm(i,n) ∑i=1ni∗ngcd(i,n)\sum_{i=1}^n \frac{i*n}{gcd(i,n)} 阅读全文 »
P3911 最小公倍数之和 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 5分钟 | 817字数 简单问题复杂化是解决问题的一个好方法。 令 cic_ici 表示 iii 出现的次数,nnn 为最大数字。 ∑i=1n∑j=1nci×cj×lcm(i,j)\sum_{i=1}^n \sum_{j=1}^nc_i \times c_j \times lcm(i,j) 阅读全文 »
P6156 简单题 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 6分钟 | 983字数 ∑i=1n∑j=1n(i+j)kf(gcd(i,j))gcd(i,j)\sum_{i=1}^n \sum_{j=1}^n (i+j)^k f(\gcd(i,j)) \gcd(i,j) i=1∑nj=1∑n(i+j)kf(gcd(i,j))gcd(i,j) 显然 f(i)=μ2(i)f(i)=\mu^2(i)f(i)=μ2(i) 阅读全文 »
P4619 [SDOI2018]旧试题 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 9分钟 | 1353字数 ∑i=1A∑j=1B∑k=1Cd(ijk)\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk) i=1∑Aj=1∑Bk=1∑Cd(ijk) ∑i=1A∑j=1B∑k=1C∑x∣i∑y∣j∑z∣k[(x,y)=1][(y,z)=1][(x,z)=1]\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{x|i}\sum_{y|j}\sum_{z|k}[(x,y)=1][(y,z)=1][(x,z)=1] 阅读全文 »
P4464 [国家集训队]JZPKIL 发布于 2020-09-12 | 分类于 莫比乌斯反演 、 伯努利数 | 11分钟 | 1781字数 如果不知道伯努利数的点这里。 ∑i=1n(i,n)x[i,n]y\sum_{i=1}^n (i,n)^x[i,n]^y i=1∑n(i,n)x[i,n]y 阅读全文 »